# 给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
#
#
#
#  示例 1：
#
#
# 输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
# 输出：[1,2,3,6,9,8,7,4,5]
#
#
#  示例 2：
#
#
# 输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
# 输出：[1,2,3,4,8,12,11,10,9,5,6,7]
#
#
#
#  Related Topics 数组 矩阵 模拟 👍 1664 👎 0

from typing import List


class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        """
        完全模拟
        """
        m, n = len(matrix), len(matrix[0])
        # 初始化边界
        left, right, top, bottom = 0, n - 1, 0, m - 1
        res: List[int] = []

        while top <= bottom and left <= right:  # 控制层的遍历
            # 从左到右遍历
            for j in range(left, right + 1):
                res.append(matrix[top][j])

            # 从上到下遍历
            for i in range(top + 1, bottom + 1):
                res.append(matrix[i][right])

            if left < right and top < bottom:
                # 从右到左遍历
                for j in range(right - 1, left, -1):
                    res.append(matrix[bottom][j])

                # 从下到上遍历
                for i in range(bottom, top, -1):
                    res.append(matrix[i][left])
            left += 1
            right -= 1
            top += 1
            bottom -= 1
        return res


# test code
if __name__ == "__main__":
    n = 3
    print(Solution().generateMatrix(n))
